#!/bin/env/python

import sys
import re

re_begin  = re.compile("^\\s*label begin_block_([A-Za-z0-9_]+:)\\s*$")
re_end    = re.compile("^\\s*label end_block_([A-Za-z0-9_]+:)\\s*$")

re_param  = re.compile("^\\s*param ([A-Za-z0-9_]+)\\s*$")
re_return = re.compile("^\\s*return ([A-Za-z0-9_]+)\\s*$")

re_assig  = re.compile("^\\s*([A-Za-z0-9_]+) := ([-?A-Za-z0-9_]+)\\s*$")
re_str    = re.compile("^\\s*([A-Za-z0-9_]+) := (\"[^\"]*\")\\s*$");
re_binop  = re.compile("^\\s*([A-Za-z0-9_]+) := ([A-Za-z0-9_]+) " + 
					  "(add|sub|mul|div|rem|slt|sle|sgt|sge|seq|sne|and|or)" + 
					  " ([A-Za-z0-9_]+)\\s*$")
re_unop   = re.compile("^\\s*([A-Za-z0-9_]+) := " + 
					  "(not|neg)" + 
					  " ([A-Za-z0-9_]+)\\s*$")

re_tmp    = re.compile("(?:^|\\s)(tmp[0-9]+)(?:$|\\s)")
re_num    = re.compile("(-?[0-9]+)")
re_extra  = re.compile("(x[0-9]+)")

re_bigtmp = re.compile("(^|\\s)tmp([89]|[1-9][0-9]+)($|\\s)")

program = sys.stdin.read().split("\n")


def merge_vars():
	# merge temps pointing to the same value into one
	equiv = {}
	assig = {}
	
	line = 0
	while line < len(program):
		tok = program[line].split(" ")
		for i in xrange(len(tok)):
			if re_tmp.match(tok[i]):
				m = re_tmp.match(tok[i])
				var = m.group(1)
				if var in assig:
					tok[i] = tok[i][:m.start(1)] + assig[var] + tok[i][m.end(1):]
					#print >> sys.stderr, "replaced", var, "with", assig[var], ":", " ".join(tok)
		curr = " ".join(tok)
		
		if re_assig.match(curr):
			m = re_assig.match(curr)
			lval = m.group(1)
			rval = m.group(2)
			if re_tmp.match(lval):
				#print >> sys.stderr, lval, rval
				if rval not in equiv:
					equiv[rval] = lval
				else:
					assig[lval] = equiv[rval]
					program.pop(line)
					continue
			elif lval in equiv:
				equiv[lval] = rval
		elif re.match("^\\s*(label begin|label end|branch-if|goto|call)([A-Za-z0-9_\\s]+:?)\\s*$", curr):
			#print >> sys.stderr, "clean!"
			equiv = {}
			assig = {}
		
		#print >> sys.stderr, line+1, stack, assig
		
		program[line] = curr
		line += 1

def invdict(d):
	# invert a dictionary
	inv = {}
	for key in d:
		if d[key] not in inv:
			inv[d[key]] = [key]
		else:
			inv[d[key]].append(key)
	return inv
			

def alive():
	# find death of each temp
	death = {}
	line = len(program) - 1
	while line >= 0:
		for temp in re_tmp.findall(program[line]):
			if temp not in death:
				death[temp] = line
		line -= 1
	
	death = invdict(death)
	#print >> sys.stderr, death
	
	pool = ["tmp%s" % i for i in xrange(8)]
	assig = {}
	
	line = 0
	while line < len(program):
		tok = program[line].split(" ")
		
		if line in death:
			for var in death[line]:
				if var in assig:
					pool.append(assig[var])
					pool.sort()
		
		for i in xrange(len(tok)):
			if re_tmp.match(tok[i]):
				m = re_tmp.match(tok[i])
				var = m.group(1)
				if var not in assig:
					assig[var] = pool.pop(0)
				tok[i] = tok[i][:m.start(1)] + assig[var] + tok[i][m.end(1):]
		
		if line in death:
			for var in death[line]:
				if var in assig:
					del assig[var]
		#print >> sys.stderr, line, assig, pool
		program[line] = " ".join(tok)
		line += 1

def promote():
	# promote temps > tmp7 to stack variables and shuffle them in tmp8 and tmp9
	stack = [0]
	
	line = 0
	while line < len(program):
		curr = re_bigtmp.sub("\\1x\\2\\3", program[line])
		pre = ""
		post = ""
		
		if re_begin.match(curr):
			stack.append(line)
			
		elif re_end.match(curr):
			stack.pop()
			
		elif re_param.match(curr):
			m = re_param.match(curr)
			if re_extra.match(m.group(1)):
				x = re_extra.match(m.group(1)).group(1)
				curr = curr[:m.start(1)] + "tmp8" + curr[m.end(1):]
				pre += "\ttmp8 := " + x + "\n"
		
		elif re_return.match(curr):
			m = re_return.match(curr)
			if re_extra.match(m.group(1)):
				x = re_extra.match(m.group(1)).group(1)
				curr = curr[:m.start(1)] + "tmp8" + curr[m.end(1):]
				pre += "\ttmp8 := " + x + "\n"
		
		elif re_binop.match(curr):
			m = re_binop.match(curr)
			
			if re_extra.match(m.group(4)):
				# op2 extra
				x = re_extra.match(m.group(4)).group(1)
				curr = curr[:m.start(4)] + "tmp9" + curr[m.end(4):]
				pre += "\ttmp9 := " + x + "\n"
				
			if re_extra.match(m.group(2)):
				# op1 extra
				x = re_extra.match(m.group(2)).group(1)
				curr = curr[:m.start(2)] + "tmp8" + curr[m.end(2):]
				pre += "\ttmp8 := " + x + "\n"
			
			if re_extra.match(m.group(1)):
				# rhs extra
				x = re_extra.match(m.group(1)).group(1)
				curr = curr[:m.start(1)] + "tmp8" + curr[m.end(1):]
				program[stack[-1]] += "\n\tint " + x
				post += "\n\t" + x + " := tmp8"
			
		elif re_unop.match(curr):
			m = re_unop.match(curr)
			
			if re_extra.match(m.group(3)):
				# op1 extra
				x = re_extra.match(m.group(3)).group(1)
				curr = curr[:m.start(3)] + "tmp8" + curr[m.end(3):]
				pre += "\ttmp8 := " + x + "\n"
			
			if re_extra.match(m.group(1)):
				#rhs extra
				x = re_extra.match(m.group(1)).group(1)
				curr = curr[:m.start(1)] + "tmp8" + curr[m.end(1):]
				program[stack[-1]] += "\n\tint " + x
				post += "\n\t" + x + " := tmp8"
		
		elif re_assig.match(curr):
			m = re_assig.match(curr)
			
			if re_extra.match(m.group(2)):
				# load extra
				x = re_extra.match(m.group(2)).group(1)
				curr = curr[:m.start(2)] + "tmp8" + curr[m.end(2):]
				pre += "\ttmp8 := " + x + "\n"
			
			if re_extra.match(m.group(1)):
				#rhs extra
				x = re_extra.match(m.group(1)).group(1)
				curr = curr[:m.start(1)] + "tmp8" + curr[m.end(1):]
				program[stack[-1]] += "\n\tint " + x
				post += "\n\t" + x + " := tmp8"
				
		elif re_str.match(curr):
			m = re_str.match(curr)
			if re_extra.match(m.group(1)):
				# rhs extra for string
				x = re_extra.match(m.group(1)).group(1)
				curr = curr[:m.start(1)] + "tmp8" + curr[m.end(1):]
				program[stack[-1]] += "\n\tint " + x
				post += "\n\t" + x + " := tmp8"
		
		program[line] = pre + curr + post
		line += 1
		

def print_program():
	for line in program:
		print line

merge_vars()
program = "\n".join(program).split("\n")
alive()
program = "\n".join(program).split("\n")
promote()
program = "\n".join(program).split("\n")
print_program()
